import java.util.Arrays;

// 统计区间中的整数数目
// 实现CountIntervals类的如下三个方法
// 1) CountIntervals() : 初始化
// 2) void add(int l, int r) : 把[l, r]范围上的数字都设置成1
// 3) int count() : 返回整个区间有多少个1
// CountIntervals类需要支持1 ~ 10^9范围
// 调用add和count方法总共10^5次
// 测试链接 : https://leetcode.cn/problems/count-integers-in-intervals/
public class Code02_CountIntervals {

    // 开点线段树的实现
    // 为了所有语言的同学都容易改出来
    // 选择用静态空间的方式实现
    // 该方法的打败比例不高但是非常好想
    // 有兴趣的同学可以研究其他做法
    class CountIntervals {

        // 支持的最大范围
        public static int n = 1000000000;

        // 空间大小定成这个值是实验的结果
        public static int LIMIT = 700001;

        public static int[] left = new int[LIMIT];

        public static int[] right = new int[LIMIT];

        public static int[] sum = new int[LIMIT];

        public static int cnt = 1;

        public CountIntervals() {
            Arrays.fill(left, 1, cnt + 1, 0);
            Arrays.fill(right, 1, cnt + 1, 0);
            Arrays.fill(sum, 1, cnt + 1, 0);
            cnt = 1;
        }

        public static void up(int h, int l, int r) {
            sum[h] = sum[l] + sum[r];
        }

        // 这个题的特殊性在于，只有改1的操作，没有改0的操作
        // 理解这个就可以分析出不需要懒更新机制，原因有两个
        // 1) 查询操作永远查的是整个范围1的数量，不会有小范围的查询，每次都返回sum[1]
        //    这意味着只要能把sum[1]更新正确即可，up函数可以保证这一点
        // 2) 一个范围已经全是1，那以后都会是1，没有必要把全是1的懒更新信息向下传递
        // 这个函数的功能比线段树能做到的范围修改功能简单很多
        // 功能有阉割就意味着存在优化的点
        public static void setOne(int jobl, int jobr, int l, int r, int i) {
            if (sum[i] == r - l + 1) {
                return;
            }
            if (jobl <= l && r <= jobr) {
                sum[i] = r - l + 1;
            } else {
                int mid = (l + r) >> 1;
                if (jobl <= mid) {
                    if (left[i] == 0) {
                        left[i] = ++cnt;
                    }
                    setOne(jobl, jobr, l, mid, left[i]);
                }
                if (jobr > mid) {
                    if (right[i] == 0) {
                        right[i] = ++cnt;
                    }
                    setOne(jobl, jobr, mid + 1, r, right[i]);
                }
                up(i, left[i], right[i]);
            }
        }

        public void add(int left, int right) {
            setOne(left, right, 1, n, 1);
        }

        public int count() {
            return sum[1];
        }
    }

}